import { testSort, measureSort } from "hy-algokit";

/**
归并排序（Merge Sort）是一种基于 分治法（Divide and Conquer）的高效排序算法，核心思想是将数组递归拆分成最小单元（通常为单个元素），再逐步合并有序的子数组，最终得到完全有序的数组。以下是详细实现和思路分析：

核心思路
分解（Divide）：
  将当前数组从中间分成左右两部分，递归地对左右子数组进行分解，直到子数组长度为1（天然有序）。

合并（Merge）：
  将两个已排序的子数组合并为一个有序数组：
  创建一个临时数组，依次比较左右子数组的元素，将较小者放入临时数组。
  将剩余未合并的元素直接追加到临时数组末尾。
  将临时数组拷贝回原数组的对应位置。
 */
// 定义一个函数，用于将一个数组进行归并排序
export default function mergeSort(arr: number[]): number[] {
  // 如果数组长度小于等于1，则直接返回该数组
  if (arr.length <= 1) return arr;
  // 计算数组的中间位置
  const mid = Math.floor(arr.length / 2);

  // 将数组分为左右两部分
  const leftArr = arr.slice(0, mid);
  const rightArr = arr.slice(mid);

  // 递归调用归并排序函数，对左右两部分进行排序
  const newLeftArr = mergeSort(leftArr);
  const newRightArr = mergeSort(rightArr);

  // 定义一个新的数组，用于存放排序后的结果
  const newArr: number[] = [];
  // 定义两个指针，分别指向左右两个数组的起始位置
  let i = 0;
  let j = 0;
  // 循环比较左右两个数组的元素，将较小的元素放入新数组中
  while (i < newLeftArr.length && j < newRightArr.length) {
    if (newLeftArr[i] < newRightArr[j]) {
      newArr.push(newLeftArr[i]);
      i++;
    } else {
      newArr.push(newRightArr[j]);
      j++;
    }
  }

  // 将left剩余的元素放入新数组中
  if (i < newLeftArr.length) {
    newArr.push(...newLeftArr.slice(i));
  }

  // 将right剩余的元素放入新数组中
  if (j < newRightArr.length) {
    newArr.push(...newRightArr.slice(j));
  }

  return newArr;
}

// testSort(mergeSort);
measureSort(mergeSort);

export {};

/**

执行顺序解释
让我们通过一个具体的例子来详细解释执行顺序。假设我们有一个数组 arr = [5, 2, 9, 1, 5, 6]，我们逐步跟踪代码的执行过程。

初始调用
初始调用 mergeSort([5, 2, 9, 1, 5, 6])：

mid = Math.floor(6 / 2) = 3
leftArr = [5, 2, 9]
rightArr = [1, 5, 6]
打印 leftArr 和 rightArr：[5, 2, 9] [1, 5, 6] ##
递归调用 mergeSort(leftArr)：

mergeSort([5, 2, 9])
mid = Math.floor(3 / 2) = 1
leftArr = [5]
rightArr = [2, 9]
打印 leftArr 和 rightArr：[5] [2, 9] ##
递归调用 mergeSort(leftArr)：

mergeSort([5])
数组长度为1，直接返回 [5]
打印 newLeftArr 和 newRightArr：[5] [] @@
递归调用 mergeSort(rightArr)：

mergeSort([2, 9])
mid = Math.floor(2 / 2) = 1
leftArr = [2]
rightArr = [9]
打印 leftArr 和 rightArr：[2] [9] ##
递归调用 mergeSort(leftArr)：

mergeSort([2])
数组长度为1，直接返回 [2]
打印 newLeftArr 和 newRightArr：[2] [] @@
递归调用 mergeSort(rightArr)：

mergeSort([9])
数组长度为1，直接返回 [9]
打印 newLeftArr 和 newRightArr：[9] [] @@
合并 [2] 和 [9]：

merge([2], [9]) 返回 [2, 9]
打印 newLeftArr 和 newRightArr：[2] [9] @@
合并 [5] 和 [2, 9]：

merge([5], [2, 9]) 返回 [2, 5, 9]
打印 newLeftArr 和 newRightArr：[5] [2, 9] @@
递归调用 mergeSort(rightArr)：

mergeSort([1, 5, 6])
mid = Math.floor(3 / 2) = 1
leftArr = [1]
rightArr = [5, 6]
打印 leftArr 和 rightArr：[1] [5, 6] ##
递归调用 mergeSort(leftArr)：

mergeSort([1])
数组长度为1，直接返回 [1]
打印 newLeftArr 和 newRightArr：[1] [] @@
递归调用 mergeSort(rightArr)：

mergeSort([5, 6])
mid = Math.floor(2 / 2) = 1
leftArr = [5]
rightArr = [6]
打印 leftArr 和 rightArr：[5] [6] ##
递归调用 mergeSort(leftArr)：

mergeSort([5])
数组长度为1，直接返回 [5]
打印 newLeftArr 和 newRightArr：[5] [] @@
递归调用 mergeSort(rightArr)：

mergeSort([6])
数组长度为1，直接返回 [6]
打印 newLeftArr 和 newRightArr：[6] [] @@
合并 [5] 和 [6]：

merge([5], [6]) 返回 [5, 6]
打印 newLeftArr 和 newRightArr：[5] [6] @@
合并 [1] 和 [5, 6]：

merge([1], [5, 6]) 返回 [1, 5, 6]
打印 newLeftArr 和 newRightArr：[1] [5, 6] @@
合并 [2, 5, 9] 和 [1, 5, 6]：

merge([2, 5, 9], [1, 5, 6]) 返回 [1, 2, 5, 5, 6, 9]
打印 newLeftArr 和 newRightArr：[2, 5, 9] [1, 5, 6] @@
递归调用的调用栈
为了更清晰地理解递归调用的过程，可以想象一个调用栈：

mergeSort([5, 2, 9, 1, 5, 6])
mergeSort([5, 2, 9])
mergeSort([5]) → 返回 [5]
mergeSort([2, 9])
mergeSort([2]) → 返回 [2]
mergeSort([9]) → 返回 [9]
merge([2], [9]) → 返回 [2, 9]
merge([5], [2, 9]) → 返回 [2, 5, 9]
mergeSort([1, 5, 6])
mergeSort([1]) → 返回 [1]
mergeSort([5, 6])
mergeSort([5]) → 返回 [5]
mergeSort([6]) → 返回 [6]
merge([5], [6]) → 返回 [5, 6]
merge([1], [5, 6]) → 返回 [1, 5, 6]
merge([2, 5, 9], [1, 5, 6]) → 返回 [1, 2, 5, 5, 6, 9]
关键点解释
递归调用的顺序：

递归调用 mergeSort 会一直深入到数组长度为1为止。
例如，mergeSort([5, 2, 9]) 会先调用 mergeSort([5])，然后调用 mergeSort([2, 9])，而 mergeSort([2, 9]) 又会先调用 mergeSort([2])，然后调用 mergeSort([9])。
打印语句的执行时机：

打印语句 console.log(leftArr, rightArr, "##") 在每次递归调用时都会执行。
但是，console.log(newLeftArr, newRightArr, "@@") 只在递归调用返回后才会执行。
因此，console.log(leftArr, rightArr, "##") 会在递归调用深入到最底层时先执行，而 console.log(newLeftArr, newRightArr, "@@") 会在递归调用返回时执行。
示例执行顺序
假设我们有数组 arr = [5, 2, 9, 1, 5, 6]，以下是详细的执行顺序：

初始调用：

mergeSort([5, 2, 9, 1, 5, 6])
打印 [5, 2, 9] [1, 5, 6] ##
递归调用 mergeSort([5, 2, 9])：

打印 [5] [2, 9] ##
递归调用 mergeSort([5])：

返回 [5]
递归调用 mergeSort([2, 9])：

打印 [2] [9] ##
递归调用 mergeSort([2])：

返回 [2]
递归调用 mergeSort([9])：

返回 [9]
合并 [2] 和 [9]：

打印 [2] [9] @@
返回 [2, 9]
合并 [5] 和 [2, 9]：

打印 [5] [2, 9] @@
返回 [2, 5, 9]
递归调用 mergeSort([1, 5, 6])：

打印 [1] [5, 6] ##
递归调用 mergeSort([1])：

返回 [1]
递归调用 mergeSort([5, 6])：

打印 [5] [6] ##
递归调用 mergeSort([5])：

返回 [5]
递归调用 mergeSort([6])：

返回 [6]
合并 [5] 和 [6]：

打印 [5] [6] @@
返回 [5, 6]
合并 [1] 和 [5, 6]：

打印 [1] [5, 6] @@
返回 [1, 5, 6]
合并 [2, 5, 9] 和 [1, 5, 6]：

打印 [2, 5, 9] [1, 5, 6] @@
返回 [1, 2, 5, 5, 6, 9]
总结
递归调用：递归调用会一直深入到数组长度为1为止。
打印语句：console.log(leftArr, rightArr, "##") 在每次递归调用时执行，而 console.log(newLeftArr, newRightArr, "@@") 在递归调用返回后执行。
执行顺序：先执行分解部分的打印语句，然后在递归返回时执行合并部分的打印语句。
 */
